package dongtaiguihua;

public class _01凑硬币 {
    //2、5、7三枚硬币数量足够，如何使用最少硬币凑出27
    public static void main(String[] args) {
        int[] a = {1,2,5};
        int aim = 11;
        Integer ans = coinChange(a,aim);
        System.out.println(ans);
    }

    private static Integer coinChange(int[] A, int M) {
        int n = A.length;
        int[] f = new int[M+1]; // 0-M
        int i,j;
        f[0] = 0 ;//init
        for (i = 1; i <=M ;++i){
            f[i] = Integer.MAX_VALUE;
            //选择硬币
            for (j = 0 ; j < n; ++j ){
                if (i >= A[j] && f[i-A[j]] != Integer.MAX_VALUE && f[i-A[j]] + 1 < f[i]){
                    f[i] = f[i-A[j]] + 1;
                }
            }
        }
        if (f[M] ==Integer.MAX_VALUE){
            return -1;
        }else {
            return f[M];
        }
    }
}
